package cnc.om.datastructure.图;

import java.util.*;

public class DAGProcessor {
    // 使用邻接表存储图结构
    private Map<String, List<String>> adjacencyList = new HashMap<>();
    private Map<String, Integer> inDegree = new HashMap<>();

    // 添加有向边
    public void addEdge(String from, String to) {
        adjacencyList.computeIfAbsent(from, k -> new ArrayList<>()).add(to);
        inDegree.put(to, inDegree.getOrDefault(to, 0) + 1);
        inDegree.putIfAbsent(from, 0);
    }

    // Kahn算法实现拓扑排序
    public List<String> topologicalSort() {
        Queue<String> queue = new LinkedList<>();
        List<String> result = new ArrayList<>();
        
        // 初始化队列（入度为0的节点）
        inDegree.forEach((node, degree) -> {
            if (degree == 0) queue.offer(node);
        });

        while (!queue.isEmpty()) {
            String current = queue.poll();
            result.add(current);
            
            // 更新相邻节点入度
            for (String neighbor : adjacencyList.getOrDefault(current, Collections.emptyList())) {
                int newDegree = inDegree.get(neighbor) - 1;
                inDegree.put(neighbor, newDegree);
                if (newDegree == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        // 检测环路（结果数量不等于节点总数说明存在环）
        if (result.size() != inDegree.size()) {
            throw new RuntimeException("图中存在环路，无法完成拓扑排序");
        }
        
        return result;
    }

    public static void main(String[] args) {
        // 实际场景示例：课程学习顺序规划
        DAGProcessor scheduler = new DAGProcessor();
        /**
         * 自动检测课程体系中的循环依赖
         * 为不同基础的学生生成个性化学习路径
         * 当用户添加新课程时动态更新推荐顺序
         * 支持大规模课程体系的快速排序（时间复杂度O(V+E)）
         */
        // 添加课程依赖关系
        scheduler.addEdge("编程基础", "数据结构");
        scheduler.addEdge("数据结构", "算法分析");
        scheduler.addEdge("离散数学", "算法分析");
        scheduler.addEdge("微积分", "机器学习");
        scheduler.addEdge("编程基础", "操作系统");
        scheduler.addEdge("操作系统", "并行计算");
        
        try {
            List<String> studyPlan = scheduler.topologicalSort();
            System.out.println("推荐学习顺序：");
            studyPlan.forEach(course -> System.out.print(course + " → "));
        } catch (RuntimeException e) {
            System.out.println(e.getMessage());
        }
    }
}
